package features.advance.leetcode.interview.huawei;

import java.util.Arrays;

/**
 *
 *  有M种字符。输入两个字符串S与P，P可空。现在在P中插入连续相同的字符，问需经过几步可由P转化为S，若不能输出-1。
 * 示例：输入：ABBCCCBAA
 * 输出：3
 *
 *
 * @author LIN
 * @date 2021-04-23
 *
 */
public class question1 {
    //区间动态规划


    public static void main(String[] args) {
        int n = 10;
        int[][] dp = new int[n+1][n+1];
        for(int r=2;r<=n;r++)//r：区间右端点，l:区间左端点
            for(int l=r-1;l>=1;l--)
                for(int k=l;k<r;k++)
                    dp[l][r] = Math.max(dp[l][r],dp[l][k]+dp[k+1][r]);
        System.out.println(Arrays.toString(dp));

    }
}
